//给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 
//
// 两个相邻元素间的距离为 1 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
//输出：[[0,0,0],[0,1,0],[0,0,0]]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
//输出：[[0,0,0],[0,1,0],[1,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 10⁴ 
// 1 <= m * n <= 10⁴ 
// mat[i][j] is either 0 or 1. 
// mat 中至少有一个 0 
// 
// Related Topics 广度优先搜索 数组 动态规划 矩阵 👍 709 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int min = Integer.MAX_VALUE;

    //    int count =0;
    public int[][] updateMatrix(int[][] mat) {
        int[][] mt = new int[mat.length][mat[0].length];

        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                if (mat[i][j] == 0) {
                    mt[i][j] = 0;
                } else {
                    int count = 0;
                    min = Integer.MAX_VALUE;
                    dfs(mat, i, j, count);
                    mt[i][j] = min;
                }

            }
        }
        return mt;
    }

    private void dfs(int[][] mat, int i, int j, int count) {

        if (i >= mat.length || j >= mat[0].length || i < 0 || j < 0 || mat[i][j] == 2) {
            return;
        }
        if (count>min) {
            return;
        }
        if (mat[i][j] == 0) {
            min = Math.min(count, min);
            return;
        }

        mat[i][j] = 2;

        dfs(mat, i + 1, j, count + 1);
        dfs(mat, i - 1, j, count + 1);
        dfs(mat, i, j + 1, count + 1);
        dfs(mat, i, j - 1, count + 1);
        mat[i][j] = 1;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
